package leetCode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class T239 {
    public static void main(String[] args) {
        new SolutionT239().maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3);
    }
}


class SolutionT239 {
    Deque<Integer> dueue=new LinkedList<>();
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[]ret=new int[nums.length-k+1];
        int retIndex=0;
        int leftIndex=0;
        int rightIndex=0;
        while (rightIndex<k-1){
            push(nums[rightIndex++]);
        }
        while (rightIndex< nums.length){
            push(nums[rightIndex++]);
            ret[retIndex++]=getMaxValue();
            pop(nums[leftIndex++]);

        }
        return ret;
    }
    public int pop(int popInt){
        if (!dueue.isEmpty()&&popInt==dueue.peek()){
            return dueue.pop();
        }
        return -1;
    }
    public void push(int pushInt){
        while (!dueue.isEmpty()&&dueue.getLast()<pushInt){
            dueue.pollLast();
        }
        dueue.offerLast(pushInt);
    }
    public int getMaxValue(){
        if (!dueue.isEmpty()){
            return dueue.getFirst();
        }
        return -1;
    }
}